//https://www.nowcoder.com/practice/ef1f53ef31ca408cada5093c8780f44b?tpId=13&tqId=1374930&ru=/exam/oj/ta&qru=/ta/coding-interviews/question-ranking&sourceUrl=%2Fexam%2Foj%2Fta%3Fpage%3D1%26tpId%3D13%26type%3D13
//思想1：插入排序实现思路；
//思想2:准备一个数组，奇数放在前面，偶数放在后面；空间换时间思想；

#include <iostream>
#include <vector>
using namespace std;

class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param array int整型vector
     * @return int整型vector
     */
    vector<int> reOrderArray(vector<int>& array) {
        if (array.empty() || array.size() < 2) return array;
        // write code here
        for (int i = 1; i < array.size(); ++i) {
            //奇数位于前面，偶数位于后面
            for ( int j = i - 1; j >= 0; --j) {
                if (((array[j] & 1) == 0) && ((array[j + 1] & 1) == 1)) {
                    //说明是个奇数,找到第一个奇数
                    std::swap(array[j], array[j + 1]);
                } else {
                    break;
                }

            }
        }
        return array;
    }
};

class Solution2 {
  public:
    vector<int> reOrderArray(vector<int>& array) {
        int n = array.size();
        vector<int> res(n);
        //统计奇数个数
        int odd = 0;
        //遍历统计
        for (int i = 0; i < n; i++) {
            if (array[i] % 2)
                odd++;
        }
        //x与y分别表示答案中奇偶数的坐标
        int x = 0, y = odd;
        for (int i = 0; i < n; i++) {
            //奇数在前
            if (array[i] % 2) {
                res[x] = array[i];
                x++;
                //偶数在后
            } else {
                res[y] = array[i];
                y++;
            }
        }
        return res;
    }
};
